package main

//可以用dfs，也可以用bfs
//如果newColor==curColor就不进行处理，所以可以不使用visited数组保存节点是否被遍历的信息
//使用一个全局变量定义上下左右节点的数组
var(
	dx = [4]int{0,0,-1,1}
	dy = [4]int{1,-1,0,0}
)
//dfs
//func floodFill(image [][]int, sr int, sc int, newColor int)[][]int{
//	//将dfs抽出来当作一个函数
//	//保存当前节点的颜色信息
//	curColor := image[sr][sc]
//	if curColor != newColor{
//		image = dfs(image, sr, sc, curColor, newColor)
//	}
//	return image
//}
//
//func dfs(image[][]int, x int, y int, curColor int, newColor int)[][]int{
//	//如果当前节点与原始节点像素一致
//	if curColor == image[x][y]{
//		//更改当前节点颜色
//		image[x][y] = newColor
//		//搜索当前节点的上下左右四个节点
//		//使用全局变量的话可以通过循环遍历上下左右节点
//		newx,newy := 0,0
//		for i:=0;i<4;i++{
//			newx = x+dx[i]
//			newy = y+dy[i]
//			//判断是否出界，以及新节点像素点是否等于原始像素点
//			if newx>=0&&newx<len(image)&&newy>=0&&newy<len(image[0])&&image[newx][newy]==curColor{
//				image = dfs(image,newx,newy,curColor,newColor)
//			}
//		}
//	}
//	return image
//}

//bfs
func floodFill(image[][]int, sr int, sc int, newColor int) [][]int{
	//保存当前节点的像素值
	curColor := image[sr][sc]
	if curColor != newColor{
		//当前节点进队列
		queue := [][]int{}
		queue = append(queue,[]int{sr,sc})
		image[sr][sc] = newColor
		//遍历数组
		newx ,newy := 0,0
		for i:=0;i<len(queue);i++{
			cell := queue[i]
			for j:=0;j<4;j++{
				//遍历上下左右
				newx = cell[0]+dx[j]
				newy = cell[1]+dy[j]
				if newx>=0&&newx<len(image)&&newy>=0&&newy<len(image[0])&&image[newx][newy]==curColor{
					//入队
					queue = append(queue, []int{newx,newy})
					image[newx][newy] = newColor
				}
			}
		}
	}
	return image
}